functor Ast (S: AST_STRUCTS): AST =
struct

open S
  
type id = Id.t
type pos = int
           
structure Binop =
struct

datatype t
  = Plus
  | Minus
  | Times
  | Divide
  | Modus
  | And
  | Or
  | Eq
  | Ne
  | Gt
  | Ge
  | Lt
  | Le
    
fun toString x =
    case x
     of Plus => " + "
      | Minus => " - "
      | Times => " * "
      | Divide => " / "
      | Modus => " % "
      | And => " && "
      | Or => " || "
      | Eq => " == "
      | Ne => " != "
      | Gt => " > "
      | Ge => " >= "
      | Lt => " < "
      | Le => " <= "
end

structure Tipe =
struct
datatype t 
  = Int
  | Char
  | Void
  | Struct of id
  | Enum of Id.t
  | Pointer of t
  | Array of t
     
val numNodesTipe = ref 0
fun numNodes x =
    let val _ = Ref.inc numNodesTipe
    in  case x
         of Int => ()
          | Char => ()
          | Void => ()
          | Struct _ => ()
          | Enum _ => ()
          | Pointer t => numNodes t
          | Array t => numNodes t
    end
          
val numNodes = fn x => (numNodes x; !numNodesTipe)

fun toString x =
    case x
     of Int => "int"
      | Char => "char"
      | Void => "void"
      | Struct id => String.concat ["struct ", Id.toString id]
      | Enum id => String.concat ["enum ", Id.toString id]
      | Pointer t => String.concat [toString t, "*"]
      | Array t => String.concat [toString t, "[]"]
end

datatype exp
  = IntNum of Intl.t
  | Lval of lval
  | Binop of exp * Binop.t * exp * pos
  | Not of exp * pos
  | Call of Id.t * (exp list) * pos   
     and lval
       = Var of Id.t * pos
       | Ptr of lval * pos
       | Array of lval * exp * pos
       | Struct of lval * Id.t * pos
       | Pstruct of lval * Id.t * pos
                    
                    
fun numNodesLval lval = 
    case lval
     of Var (id, pos) => 2
      | Ptr (lval, pos) => (numNodesLval lval) + 1
      | Array (lval, exp, pos) => (numNodesLval lval) + (numNodesExp exp) + 1
      | Struct (lval, id, pos) => (numNodesLval lval) + 2
      | Pstruct (lval, id, pos) => (numNodesLval lval) + 2
and numNodesExp exp = 
    case exp
     of IntNum i => 2
      | Lval lval => (numNodesLval lval) + 1
      | Binop (exp1,opr,exp2,pos) => (numNodesExp exp1)+(numNodesExp exp2)+2 (* 2=opr+Binop*)
      | Not (exp,pos) => (numNodesExp exp)+1
and numNodesExps exps = 
    case exps
     of [] => 0
      | exp :: exps => (numNodesExp exp)+(numNodesExps exps)
          
       
fun expToString exp = raise Fail "to do"
and lvalToString lval = 
    case lval
     of Var (id, pos) => Id.toString id
      | Ptr (lval1, pos) => String.concat ["*(", lvalToString lval1, ")"]
      | Array (lval1, exp, pos) => String.concat [lvalToString lval1, "[", expToString exp, "]"]
      | Struct (lval1, id, pos) => String.concat [lvalToString lval1, ".", Id.toString id]
      | Pstruct (lval1, id, pos) => String.concat [lvalToString lval1, "->", Id.toString id]
fun expsToString es =
     case es
       of [] => ""
        | [e] => expToString e
        | x :: xs => String.concat [expToString x, ", ", expsToString xs]
        
fun space n =
    case n
     of 0 => ""
      | i => String.concat [" ", space (i - 1)]
  
structure Lval =
struct
type exp = exp
datatype t = datatype lval
   
val toString = lvalToString

end
  
structure Exp =
struct
type bop = Binop.t
type lval = lval
datatype t = datatype exp
    
val toString = expToString

end

structure Dec =
struct
datatype t 
  = StructDec of {name: id,
                  fields : {name: id, ty: Tipe.t} list}
  | EnumDec of {name: id,
                fields: id list}
  | VarDec of {name: id,
               ty: Tipe.t}
  | FunDec of {name: id,
               rettype: Tipe.t,
               args: {name: id, ty: Tipe.t} list}
               
fun toString s = raise Fail "to do"

end


structure Stm =
struct

type dec = Dec.t
type lval = Lval.t
type exp = Exp.t
datatype t 
  = Assign of lval * exp * pos
  | Comp of {decs: dec list, stms: t list, pos: pos}
  | If of {condition: Exp.t, thenn: t, elsee: t option, pos: pos}
  | While of {condition: Exp.t, body: t, pos: pos}
  | Return of Exp.t option * pos
           
fun numNodes x = raise Fail "to do"

fun toString x = raise Fail "to do"    

end
  


structure Fun =
struct

datatype t
  = T of {name: id,
          rettype: Tipe.t,
          args: {name : id, ty: Tipe.t} list,
          stm: Stm.t}
              
fun numNodes (T {name,
                 rettype,
                 args,
                 stm}) =
    List.length args + Stm.numNodes stm + 3
    
fun ppArgs args =
    case args
     of [] => ""
      | [{name, ty}] => String.concat [Tipe.toString ty, " ", Id.toString name]
      | {name, ty} :: xs => String.concat [Tipe.toString ty, " ", Id.toString name, ", ", ppArgs xs]
                      
fun toString f =
    case f
     of T {name,
           rettype,
           args,
           stm} =>
        String.concat [Tipe.toString rettype, " ", Id.toString name, "(", ppArgs args, ")\n",
                       "{\n",
                       Stm.toString stm,
                       "}\n\n\n"]
end

structure Top =
struct

type f = Fun.t
type dec = Dec.t

datatype t 
  = Dec of dec
  | Fun of f

val toString = raise Fail "to do"

end

structure Program =
struct

type top = Top.t

datatype t
  = T of top list
         
fun bogus () = T []
               
fun numNodes x = raise Fail "to do"
    
fun toString x = raise Fail "to do"
    
end

end
